package com.study.tree;

import java.util.Arrays;
import java.util.StringJoiner;

public class MaxHeap {
    private Integer[] values;
    private int length;

    public MaxHeap(Integer[] array) {
//      构建堆
        this.length = array.length;
//        找出最后一个非叶子节点，也就是 left(i) <= length 2 ====> 2 * i + 1 <= length -1  =====> i =   (length - 2) /2
        this.values = Arrays.copyOf(array, array.length);
        for (int i = (length - 2) / 2; i >= 0; i--) {
            maxHeapFy(i);
        }
    }

    private void maxHeapFy(Integer i) {
//        这段代码很容易写错 每次循环必须刷新root,如果使用i变量容易遗漏，所以用root存当前节点
        Integer largest = null;
        Integer root = i;
        Boolean exchange = true;
        while (exchange) {
            exchange = false;
            largest = root;
            Integer l = left(root);
            Integer r = right(root);
            if (l != null && values[largest] < values[l]) largest = l;
            if (r != null && values[largest] < values[r]) largest = r;
            if (!root.equals(largest)) {
                swap(root, largest);
                exchange = true;
                root = largest;
            }

        }
    }

    private Integer left(Integer i) {
        //        这里犯了个错误，边界值，得注意
        if (2 * i + 1 <= length - 1) return 2 * i + 1;
        return null;
    }

    private Integer right(Integer i) {
//        这里犯了个错误，边界值，得注意
        if (2 * i + 2 <= length - 1) return 2 * i + 2;
        return null;
    }

    private void swap(int i, int j) {
        Integer temp = values[i];
        values[i] = values[j];
        values[j] = temp;
    }

    public void printArr() {
        StringJoiner stringJoiner = new StringJoiner(",");

        for (Integer i : values) {
            stringJoiner.add(i.toString());
        }
        System.out.println(stringJoiner.toString());
    }

    public static void main(String[] args) {

        Integer[] arr = {4, 6, 2, 77, 44, 9, 7, 62, 11, 45, 66};
        MaxHeap maxHeap = new MaxHeap(arr);
        maxHeap.printArr();
    }

}





